| 翻訳と辞書 |
| kinetic tournament ： ウィキペディア英語版 |
kinetic tournament
A Kinetic Tournament is a kinetic data structure that functions as a priority queue for elements whose priorities change as a continuous function of time. It is implemented analogously to a "tournament" between elements to determine the "winner" (maximum or minimum element), with the certificates enforcing the winner of each "match" in the tournament. It supports the usual priority queue operations - ''insert'', ''delete'' and ''find-max''. They are often used as components of other kinetic data structures, such as kinetic closest pair.
== Implementation ==
A kinetic tournament is organized in a binary tree-like structure, where the leaves contain the elements, and each internal node contains the larger (or smaller) of the elements in its child nodes. Thus, the root of the tree contains the maximum (or minimum) element at a given time.
The validity of the structure is enforced by creating a certificate at each node, which asserts that the element in the node is the larger of the two children. When this certificate fails, the element at the node is changed (to be the element in the other child), and a new certificate representing the new invariant is created. If the element this node was a winner at its parent node, then the element and certificates at the parent must be recursively updated too.
抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』
■ウィキペディアで「kinetic tournament」の詳細全文を読む
スポンサード リンク
| 翻訳と辞書 : 翻訳のためのインターネットリソース |
Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.
|
|